package leetcode;

class Solution_134 {
    /**
     * 暴力解法，超时
     * @param gas 每个加油站的油量
     * @param cost 从第i个加油站到第i+1个加油站需要的油量
     * @return
     */
    public int canCompleteCircuit_OutTime(int[] gas, int[] cost) {
        int remain = 0; //剩余油量
        int start = 0; //起点
        int cur = 0; //当前位置
        while(start < gas.length){
            remain = gas[cur % gas.length] + remain - cost[cur % gas.length];
            if (remain >= 0){
                if (cur - start == gas.length){//如果跑满一圈了
                    return start;
                }
                cur = cur + 1;
            }else {
                start ++;
                cur = start;
                remain = 0;
            }
        }
        return -1;
    }
    // 解法2
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            curSum += gas[i] - cost[i];
            totalSum += gas[i] - cost[i];
            if (curSum < 0) {
                index = (i + 1) % gas.length ;
                curSum = 0;
            }
        }
        if (totalSum < 0) return -1;
        return index;
    }

    public static void main(String[] args) {
        Solution_134 test = new Solution_134();
        System.out.println(test.canCompleteCircuit(new int[]{1,2,3,4,5},new int[]{3,4,5,1,2}) == 3);
        System.out.println(test.canCompleteCircuit(new int[]{2,3,4},new int[]{3,4,3}) == -1);
        System.out.println(test.canCompleteCircuit(new int[]{4,5,3,1,4},new int[]{5,4,3,4,2}) == -1);
    }
}